package 算法.动态规划;

public class JZ47礼物的最大价值 {
    //动态规划
    public int maxValue (int[][] grid) {
        // write code here
        int m = grid.length;
        int n = grid[0].length;
        //第一列只能来自上方
        for(int i=1;i<m;i++)
            grid[i][0] += grid[i-1][0];
        //第一行只能来自左边
        for(int i=1;i<n;i++)
            grid[0][i] += grid[0][i-1];
        //遍历后续每一个位置
        for(int i=1;i<m;i++)
            for(int j=1;j<n;j++)
                //增加来自左边的与上边的之间的较大值
                grid[i][j] += Math.max(grid[i-1][j] , grid[i][j-1]);
        return  grid[m-1][n-1];
    }

    //记忆化递归（扩展思路）
    public int maxValue2 (int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        //用于记忆递归过程中的值
        int[][] dp = new int[m][n];
        return recursion(grid, m - 1, n - 1, dp);
    }

    private int recursion(int[][] grid, int m, int n, int[][] dp){
        //到达起点
        if( m==0 && n==0 ){
            dp[0][0] = grid[0][0];
            return  grid[0][0];
        }
        //两个边界
        if( m==0 )
            dp[0][n] = grid[0][n] + recursion(grid,m,n-1,dp);
        if( n==0 )
            dp[m][0] = grid[m][0] + recursion(grid,m-1,n,dp);
        //如果有值可以直接返回
        if(dp[m][n] == 0)
            //递归求左边或者上边的最大值
            dp[m][n] = grid[m][n] + Math.max(recursion(grid, m - 1, n, dp), recursion(grid, m, n - 1, dp));
        return  dp[m][n];
    }
}
